package features.advance.leetcode.geometry.stack.easy;

import java.util.*;

/**
 * 20. 有效的括号
 * 难度  简单
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
 *
 * 有效字符串需满足：
 *
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 注意空字符串可被认为是有效字符串。
 *
 * 示例 1:
 *
 * 输入: "()"
 * 输出: true
 * 示例 2:
 *
 * 输入: "()[]{}"
 * 输出: true
 * 示例 3:
 *
 * 输入: "(]"
 * 输出: false
 * 示例 4:
 *
 * 输入: "([)]"
 * 输出: false
 * 示例 5:
 *
 * 输入: "{[]}"
 * 输出: true
 *
 * @author LIN
 */
public class Solution20 {
    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }

        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char a = !stack.isEmpty() ? stack.get(stack.size() - 1) : s.charAt(i);

            if (parseChar(a) != s.charAt(i)){
                stack.add(s.charAt(i));
            }else {
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
    public char parseChar(char a){
        switch (a){
            case '(':
                return ')';
            case '[':
                return ']';
            case '{':
                return '}';
            default:
                return '0';

        }

    }
    public static void main(String[] args) {
        boolean valid = false;
        String s = "[)(]";

//        s = "()[]{}";
        s= "{[]}";
        s="(([]){})";// 得修改str字符串，去掉匹配的字符
        valid = new Solution20(){
            @Override
            public boolean isValid(String s) {
                int n = s.length();
                if (n % 2 == 1) {
                    return false;
                }
                Map<Character, Character> pairs = new HashMap<Character, Character>() {{
                    put(')', '(');
                    put(']', '[');
                    put('}', '{');
                }};
                Deque<Character> stack = new LinkedList<Character>();
                for (int i = 0; i < n; i++) {
                    char ch = s.charAt(i);
                    if (pairs.containsKey(ch)) {
                        if (stack.isEmpty() || !stack.peek().equals(pairs.get(ch))) {
                            return false;
                        }
                        stack.pop();
                    } else {
                        stack.push(ch);
                    }
                }
                return stack.isEmpty();
            }
        }.isValid(s);
        System.out.println(valid);
    }



}
